class Solution {
public:

    // 50. Pow(x, n) 快速幂
    // https://leetcode.cn/problems/powx-n/
    double myPow(double x, int n) {
        return n<0 ? 1.0/Pow(x, -(long)n) : Pow(x, n);
    }

    double Pow(double x, long n) {
        if (n == 0) return 1;
        double tmp = myPow(x, n/2);
        return n&1 ? tmp*tmp*x : tmp*tmp;
    }

    ///////////////////////////////////////////////////////////////////////////////
    // 2331. 计算布尔二叉树的值
    // https://leetcode.cn/problems/evaluate-boolean-binary-tree/
    bool evaluateTree(TreeNode* root) {
        if (root->val == 1) return 1;
        if (root->val == 0) return 0;

        bool left = evaluateTree(root->left);
        bool right = evaluateTree(root->right);

        return root->val == 2 ? left||right : left&&right;
    }

    ///////////////////////////////////////////////////////////////////////////////
    // 129. 求根节点到叶节点数字之和
    // https://leetcode.cn/problems/sum-root-to-leaf-numbers/description/
    void dfs(TreeNode* root, int num, int& ans)
    {
        if (root == nullptr) return ;
        if (root->left==nullptr && root->right==nullptr)
        {
            ans += num + root->val;
            return ;
        }
        
        num += root->val;
        dfs(root->left, num*10, ans);
        dfs(root->right, num*10, ans);
    }

    int sumNumbers(TreeNode* root) {
        if (root == nullptr) return 0;
        int ans = 0;
        dfs(root, 0, ans);
        return ans;
    }
};